package com.lfg.leetcode.leetcode1000;


import java.util.*;

public class No1311watchedVideosByFriends {
    public static void main(String[] args) {

        List<String> list = new ArrayList<>();
        list.add("aa");
        list.add("a");
        list.add("abcsi");
        list.add("ag");
        list.add("ail");
        list.add("akhuwa");
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                int length = Math.min(o1.length(), o2.length());
                for (int i = 0; i < length; i++) {
                    int i1 = o1.charAt(i) - o2.charAt(i);
                    if (i1 == 0) {
                        continue;
                    }
                    return i1;
                }
                return o1.length() - o2.length();
            }
        });


        List<List<String>> watchedVideos = new ArrayList<>();
        watchedVideos.add(new ArrayList<>(Arrays.asList("A,B".split(","))));
        watchedVideos.add(new ArrayList<>(Arrays.asList("abc,aby".split(","))));
        watchedVideos.add(new ArrayList<>(Arrays.asList("abc,aby".split(","))));
        watchedVideos.add(new ArrayList<>(Arrays.asList("D".split(","))));
        int[][] friends = new int[][]{new int[]{1, 2}, {0, 3}, {0, 3}, {1, 2}};
        int id = 0, level = 1;
        System.out.println(watchedVideosByFriends(watchedVideos, friends, id, level));
    }

    public static List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {
        List<String> ret = new ArrayList<>();

        Queue<Integer> queue = new LinkedList<>();
        queue.add(id);
        Set<Integer> visited = new HashSet<>();
        visited.add(id);
        while(level > 0){
            int size = queue.size();
            for(int i= 0;i<size;i++){
                Integer n = queue.poll();
                if(null == n){
                    continue;
                }
                visited.add(n);
                for(int m : friends[n]){
                    if(visited.contains(m)){
                        continue;
                    }
                    visited.add(m);
                    queue.offer(m);
                }
            }
            level--;
        }


        Map<String, Integer> video = new HashMap<>();
        for (int i : queue) {
            for (String v : watchedVideos.get(i)) {
                Integer cnt = video.get(v);
                if (cnt == null) {
                    cnt = 1;
                } else {
                    cnt += 1;
                }
                video.put(v, cnt);
            }
        }

        List<Map.Entry<String, Integer>> set = new ArrayList<>(video.entrySet());
        Collections.sort(set, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().equals(o2.getValue())) {
                    int i = 0;
                    while (true) {
                        if (o1.getKey().charAt(i) != o2.getKey().charAt(i)) {
                            return o1.getKey().charAt(i) - o2.getKey().charAt(i);
                        } else {
                            i++;
                            if (i >= Math.min(o1.getKey().length(), o2.getKey().length())) {
                                return o1.getKey().length() - o2.getKey().length();
                            }
                        }
                    }
                }
                return o1.getValue() - o2.getValue();
            }
        });
        for (Map.Entry<String, Integer> entry : set) {
            System.out.print(entry.getKey() + "=" + entry.getValue() + ", ");
            ret.add(entry.getKey());
        }
        return ret;
    }

}

